package main

import "fmt"

func minPathSum(grid [][]int) int {
	// 暴力递归超时
	// return grid[0][0] + min(f(grid, 0, 1), f(grid, 1, 0))

	// 通过规律找二维表（逆向计算）
	m := len(grid)
	n := len(grid[0])
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			grid[i][j] = grid[i][j] + minRightBottom(grid, i, j)
		}
	}
	return grid[0][0]
}
func minRightBottom(grid [][]int, i, j int) int {
	if i+1 == len(grid) && j+1 == len(grid[0]) {
		return 0
	} else if i+1 == len(grid) {
		return grid[i][j+1]
	} else if j+1 == len(grid[0]) {
		return grid[i+1][j]
	} else {
		if grid[i][j+1] < grid[i+1][j] {
			return grid[i][j+1]
		} else {
			return grid[i+1][j]
		}
	}
}

// 递归不可行，会超时
// 从位置 (i,j) 到右下角的最小值
func f(grid [][]int, i int, j int) int {
	if i >= len(grid) && j >= len(grid[0]) {
		return 201
	} else if i >= len(grid) {
		return 201
	} else if j >= len(grid[0]) {
		return 201
	} else {
		return grid[i][j] + min(f(grid, i+1, j), f(grid, i, j+1))
	}
}

func min(a, b int) int {
	if a == 201 && b == 201 {
		return 0
	}
	if a < b {
		return a
	} else {
		return b
	}
}

func main() {
	input := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}
	fmt.Println(7, minPathSum(input))
	input = [][]int{{1}}
	fmt.Println(1, minPathSum(input))
	input = [][]int{{1, 2, 3, 4, 5}}
	fmt.Println(15, minPathSum(input))
}
